//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复
//的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例： 
//
// 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
// 
// Related Topics 数组 双指针 
// 👍 2476 👎 0

package leetcode.editor.cn;

import java.util.*;

//Java：三数之和
public class P15ThreeSum {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * 思路: 参考了网上的思路，先排序，然后遍历i ，计算i + 后面的两个数 [j指针从左到右，k指针从右到左] 的和是否大于0，>0 ,k左移， < 0, j 右移, =0， k左移且 j 右移
     *
     *      去重的话，有两种情况，
     *      一是 i 和前一位重复:
     *                  if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
     *                     continue;
     *                  }
     *      二是，k左移且 j 右移 的结果和之前的重复:
     *                  if (k + 1 < nums.length && j - 1 >= 0) {
     *                      if (nums[k + 1] == nums[k] && nums[j - 1] == nums[j]) {
     *                          k--;
     *                          j++;
     *                          continue;
     *                      }
     *                  }
     *
     *
     * 执行用时： 22 ms , 在所有 Java 提交中击败了 94.65% 的用户 内存消耗： 43.8 MB , 在所有 Java 提交中击败了 59.06% 的用户
     *
     */
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> list = new ArrayList<>();

            // 1.排序
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 2; i++) {
                // 2.i 大于0，之后的数说明都是大于0，就不用算了
                if (nums[i] > 0) {
                    break;
                }
                // 3.i 和前一位一样，就不用算了
                if (i - 1 >= 0 && nums[i] == nums[i - 1]) {
                    continue;
                }

                int j = i + 1;
                int k = nums.length - 1;

                while (j < k) {
                    int sum = nums[i] + nums[j] + nums[k];
                    if (sum > 0) {
                        k--;
                    } else if (sum < 0) {
                        j++;
                    } else {
                        // 4.去重复        -2, 0, 0, 2, 2 的情况，已经算了第一个 -2[i=0] 0[j=1] 2[k=4] ，再算 -2[i=0]  0[j=2] 2[k=3]时，判断相等就不用算了
                        if (k + 1 < nums.length && j - 1 >= 0) {
                            if (nums[k + 1] == nums[k] && nums[j - 1] == nums[j]) {
                                k--;
                                j++;
                                continue;
                            }
                        }
                        List<Integer> tempList = new ArrayList<>();
                        tempList.add(nums[i]);
                        tempList.add(nums[j]);
                        tempList.add(nums[k]);
                        list.add(tempList);
                        k--;
                        j++;
                    }
                }
            }
            return list;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 0, 0, 2, 2};
        Solution solution = new P15ThreeSum().new Solution();
        System.out.println(solution.threeSum(nums).toString());
        // TO TEST
    }

}